package tree;

import pojo.TreeNode;

public class SameTreeUtils {

    /**
     * 功能描述: 判断两颗树是否为同一颗树
     *
     * @param root1
     * @param root2
     * @return boolean
     */
    public static  boolean isSameTree(TreeNode root1,
                                      TreeNode root2){
        /***
         * 如果root1和root2都为null，那么异或结果为false。
         * 如果root1和root2都不为null，那么异或结果也为false。
         * 只有当root1和root2中只有一个为null时，异或结果才为true。
         */
        if (root1 == null ^ root2 == null){
            return false;
        }

        if (root1 ==null && root2 == null){
            return true;
        }

        // 1. 当前节点相等，并且左子树相等,右子树相等
        return root1.equals(root2) && isSameTree(root1.left,root2.left) && isSameTree(root1.right,root2.right);
    }

    public static void main(String[] args) {
        TreeNode root1 = generateTree();
        TreeNode root2 = generateTree();

        System.out.println(isSameTree(root1,
                                      root2));

        TreeNode root3 = generateTree2();
        System.out.println(isSameTree(root1,
                                      root3));
    }

    private static TreeNode generateTree() {
        TreeNode treeNode = new TreeNode(1,
                                         "1");
        treeNode.left = new TreeNode(2,
                                     "2");
        treeNode.right = new TreeNode(2,
                                      "2");

        treeNode.left.left = new TreeNode(4,
                                          "4");

        treeNode.left.right = new TreeNode(5,
                                           "5");

        treeNode.right.left = new TreeNode(5,
                                           "5");
        treeNode.right.right = new TreeNode(4,
                                            "4");

        return treeNode;
    }

    private static TreeNode generateTree2() {
        TreeNode treeNode = new TreeNode(1,
                                         "1");
        treeNode.left = new TreeNode(2,
                                     "2");
        treeNode.right = new TreeNode(2,
                                      "2");

        treeNode.left.left = new TreeNode(4,
                                          "4");

        treeNode.left.right = new TreeNode(5,
                                           "5");

        treeNode.right.left = new TreeNode(5,
                                           "5");
        treeNode.right.right = new TreeNode(4,
                                            "11");

        return treeNode;
    }
}
